package arithmetic.LeetCode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 347. 前 K 个高频元素
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 *
 *  示例 1:
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 *
 * 示例 2:
 * 输入: nums = [1], k = 1
 * 输出: [1]
 *
 * https://leetcode.cn/problems/top-k-frequent-elements/
 * @author jiangfeng on 2023/4/25
 */
public class TopKFrequent {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution().topKFrequent(new int[] {1, 1, 1, 2, 2, 3}, 2)));
    }
    static class  Solution {
        public int[] topKFrequent(int[] nums, int k) {
            // 设计一个最大堆,
            Map<Integer,Integer> map = new HashMap();
            for(int i:nums){
                map.put(i,map.getOrDefault(i,0)+1);
            }
            // 用堆来维护前n个元素.
            PriorityQueue<int[]> q = new PriorityQueue<>(k,Comparator.comparingInt((int[] a)->a[1]).reversed());
            int j=0;
            for(int key:map.keySet()){
                q.offer(new int[]{key,map.get(key)});
            }
            int[] res = new int[k];
            for(int i=0;i<k;i++){
                int[] poll = q.poll();
                res[i]=poll[0];
            }
            return res;
        }
    }

    static class  Solution1 {
        public int[] topKFrequent(int[] nums, int k) {
            Map<Integer,Integer> map = new HashMap();
            for(int i:nums){
                map.put(i,map.getOrDefault(i,0)+1);
            }
            int[][] a = new int[map.size()][2];
            int j=0;
            for(int i:map.keySet()){
                a[j][0]=i;
                a[j++][1]=map.get(i);
            }
            Arrays.sort(a, Comparator.comparingInt((int[] b)->b[1]).reversed());
            int[] res = new int[k];
            for(int i=0;i<k;i++){
                res[i]=a[i][0];
            }
            return res;

        }
    }
}
